'Weak Dependency Graph [60.0]'
------------------------------
Answer: YES(?,O(n^1))
Input Problem: innermost runtime-complexity with respect to
Rules:
{ f(x, nil()) -> g(nil(), x)
, f(x, g(y, z)) -> g(f(x, y), z)
, ++(x, nil()) -> x
, ++(x, g(y, z)) -> g(++(x, y), z)
, null(nil()) -> true()
, null(g(x, y)) -> false()
, mem(nil(), y) -> false()
, mem(g(x, y), z) -> or(=(y, z), mem(x, z))
, mem(x, max(x)) -> not(null(x))
, max(g(g(nil(), x), y)) -> max'(x, y)
, max(g(g(g(x, y), z), u())) -> max'(max(g(g(x, y), z)), u())}
Details:
We have computed the following set of weak (innermost) dependency pairs:
{ f^#(x, nil()) -> c_0()
, f^#(x, g(y, z)) -> c_1(f^#(x, y))
, ++^#(x, nil()) -> c_2()
, ++^#(x, g(y, z)) -> c_3(++^#(x, y))
, null^#(nil()) -> c_4()
, null^#(g(x, y)) -> c_5()
, mem^#(nil(), y) -> c_6()
, mem^#(g(x, y), z) -> c_7(mem^#(x, z))
, mem^#(x, max(x)) -> c_8(null^#(x))
, max^#(g(g(nil(), x), y)) -> c_9()
, max^#(g(g(g(x, y), z), u())) -> c_10(max^#(g(g(x, y), z)))}
The usable rules are:
{}
The estimated dependency graph contains the following edges:
{f^#(x, g(y, z)) -> c_1(f^#(x, y))}
==> {f^#(x, g(y, z)) -> c_1(f^#(x, y))}
{f^#(x, g(y, z)) -> c_1(f^#(x, y))}
==> {f^#(x, nil()) -> c_0()}
{++^#(x, g(y, z)) -> c_3(++^#(x, y))}
==> {++^#(x, g(y, z)) -> c_3(++^#(x, y))}
{++^#(x, g(y, z)) -> c_3(++^#(x, y))}
==> {++^#(x, nil()) -> c_2()}
{mem^#(g(x, y), z) -> c_7(mem^#(x, z))}
==> {mem^#(x, max(x)) -> c_8(null^#(x))}
{mem^#(g(x, y), z) -> c_7(mem^#(x, z))}
==> {mem^#(g(x, y), z) -> c_7(mem^#(x, z))}
{mem^#(g(x, y), z) -> c_7(mem^#(x, z))}
==> {mem^#(nil(), y) -> c_6()}
{mem^#(x, max(x)) -> c_8(null^#(x))}
==> {null^#(g(x, y)) -> c_5()}
{mem^#(x, max(x)) -> c_8(null^#(x))}
==> {null^#(nil()) -> c_4()}
{max^#(g(g(g(x, y), z), u())) -> c_10(max^#(g(g(x, y), z)))}
==> {max^#(g(g(g(x, y), z), u())) -> c_10(max^#(g(g(x, y), z)))}
{max^#(g(g(g(x, y), z), u())) -> c_10(max^#(g(g(x, y), z)))}
==> {max^#(g(g(nil(), x), y)) -> c_9()}
We consider the following path(s):
1) { max^#(g(g(g(x, y), z), u())) -> c_10(max^#(g(g(x, y), z)))
, max^#(g(g(nil(), x), y)) -> c_9()}
The usable rules for this path are empty.
We have oriented the usable rules with the following strongly linear interpretation:
Interpretation Functions:
f(x1, x2) = [0] x1 + [0] x2 + [0]
nil() = [0]
g(x1, x2) = [0] x1 + [0] x2 + [0]
++(x1, x2) = [0] x1 + [0] x2 + [0]
null(x1) = [0] x1 + [0]
true() = [0]
false() = [0]
mem(x1, x2) = [0] x1 + [0] x2 + [0]
or(x1, x2) = [0] x1 + [0] x2 + [0]
=(x1, x2) = [0] x1 + [0] x2 + [0]
max(x1) = [0] x1 + [0]
not(x1) = [0] x1 + [0]
max'(x1, x2) = [0] x1 + [0] x2 + [0]
u() = [0]
f^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_0() = [0]
c_1(x1) = [0] x1 + [0]
++^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_2() = [0]
c_3(x1) = [0] x1 + [0]
null^#(x1) = [0] x1 + [0]
c_4() = [0]
c_5() = [0]
mem^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_6() = [0]
c_7(x1) = [0] x1 + [0]
c_8(x1) = [0] x1 + [0]
max^#(x1) = [0] x1 + [0]
c_9() = [0]
c_10(x1) = [0] x1 + [0]
We have applied the subprocessor on the resulting DP-problem:
'Weight Gap Principle'
----------------------
Answer: YES(?,O(n^1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {max^#(g(g(nil(), x), y)) -> c_9()}
Weak Rules:
{max^#(g(g(g(x, y), z), u())) -> c_10(max^#(g(g(x, y), z)))}
Details:
We apply the weight gap principle, strictly orienting the rules
{max^#(g(g(nil(), x), y)) -> c_9()}
and weakly orienting the rules
{max^#(g(g(g(x, y), z), u())) -> c_10(max^#(g(g(x, y), z)))}
using the following strongly linear interpretation:
Processor 'Matrix Interpretation' oriented the following rules strictly:
{max^#(g(g(nil(), x), y)) -> c_9()}
Details:
Interpretation Functions:
f(x1, x2) = [0] x1 + [0] x2 + [0]
nil() = [0]
g(x1, x2) = [1] x1 + [1] x2 + [0]
++(x1, x2) = [0] x1 + [0] x2 + [0]
null(x1) = [0] x1 + [0]
true() = [0]
false() = [0]
mem(x1, x2) = [0] x1 + [0] x2 + [0]
or(x1, x2) = [0] x1 + [0] x2 + [0]
=(x1, x2) = [0] x1 + [0] x2 + [0]
max(x1) = [0] x1 + [0]
not(x1) = [0] x1 + [0]
max'(x1, x2) = [0] x1 + [0] x2 + [0]
u() = [0]
f^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_0() = [0]
c_1(x1) = [0] x1 + [0]
++^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_2() = [0]
c_3(x1) = [0] x1 + [0]
null^#(x1) = [0] x1 + [0]
c_4() = [0]
c_5() = [0]
mem^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_6() = [0]
c_7(x1) = [0] x1 + [0]
c_8(x1) = [0] x1 + [0]
max^#(x1) = [1] x1 + [1]
c_9() = [0]
c_10(x1) = [1] x1 + [0]
Finally we apply the subprocessor
'Empty TRS'
-----------
Answer: YES(?,O(1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {}
Weak Rules:
{ max^#(g(g(nil(), x), y)) -> c_9()
, max^#(g(g(g(x, y), z), u())) -> c_10(max^#(g(g(x, y), z)))}
Details:
The given problem does not contain any strict rules
2) {max^#(g(g(g(x, y), z), u())) -> c_10(max^#(g(g(x, y), z)))}
The usable rules for this path are empty.
We have oriented the usable rules with the following strongly linear interpretation:
Interpretation Functions:
f(x1, x2) = [0] x1 + [0] x2 + [0]
nil() = [0]
g(x1, x2) = [0] x1 + [0] x2 + [0]
++(x1, x2) = [0] x1 + [0] x2 + [0]
null(x1) = [0] x1 + [0]
true() = [0]
false() = [0]
mem(x1, x2) = [0] x1 + [0] x2 + [0]
or(x1, x2) = [0] x1 + [0] x2 + [0]
=(x1, x2) = [0] x1 + [0] x2 + [0]
max(x1) = [0] x1 + [0]
not(x1) = [0] x1 + [0]
max'(x1, x2) = [0] x1 + [0] x2 + [0]
u() = [0]
f^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_0() = [0]
c_1(x1) = [0] x1 + [0]
++^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_2() = [0]
c_3(x1) = [0] x1 + [0]
null^#(x1) = [0] x1 + [0]
c_4() = [0]
c_5() = [0]
mem^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_6() = [0]
c_7(x1) = [0] x1 + [0]
c_8(x1) = [0] x1 + [0]
max^#(x1) = [0] x1 + [0]
c_9() = [0]
c_10(x1) = [0] x1 + [0]
We have applied the subprocessor on the resulting DP-problem:
'Weight Gap Principle'
----------------------
Answer: YES(?,O(n^1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules:
{max^#(g(g(g(x, y), z), u())) -> c_10(max^#(g(g(x, y), z)))}
Weak Rules: {}
Details:
We apply the weight gap principle, strictly orienting the rules
{max^#(g(g(g(x, y), z), u())) -> c_10(max^#(g(g(x, y), z)))}
and weakly orienting the rules
{}
using the following strongly linear interpretation:
Processor 'Matrix Interpretation' oriented the following rules strictly:
{max^#(g(g(g(x, y), z), u())) -> c_10(max^#(g(g(x, y), z)))}
Details:
Interpretation Functions:
f(x1, x2) = [0] x1 + [0] x2 + [0]
nil() = [0]
g(x1, x2) = [1] x1 + [1] x2 + [8]
++(x1, x2) = [0] x1 + [0] x2 + [0]
null(x1) = [0] x1 + [0]
true() = [0]
false() = [0]
mem(x1, x2) = [0] x1 + [0] x2 + [0]
or(x1, x2) = [0] x1 + [0] x2 + [0]
=(x1, x2) = [0] x1 + [0] x2 + [0]
max(x1) = [0] x1 + [0]
not(x1) = [0] x1 + [0]
max'(x1, x2) = [0] x1 + [0] x2 + [0]
u() = [0]
f^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_0() = [0]
c_1(x1) = [0] x1 + [0]
++^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_2() = [0]
c_3(x1) = [0] x1 + [0]
null^#(x1) = [0] x1 + [0]
c_4() = [0]
c_5() = [0]
mem^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_6() = [0]
c_7(x1) = [0] x1 + [0]
c_8(x1) = [0] x1 + [0]
max^#(x1) = [1] x1 + [8]
c_9() = [0]
c_10(x1) = [1] x1 + [0]
Finally we apply the subprocessor
'Empty TRS'
-----------
Answer: YES(?,O(1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {}
Weak Rules:
{max^#(g(g(g(x, y), z), u())) -> c_10(max^#(g(g(x, y), z)))}
Details:
The given problem does not contain any strict rules
3) { mem^#(g(x, y), z) -> c_7(mem^#(x, z))
, mem^#(x, max(x)) -> c_8(null^#(x))
, null^#(g(x, y)) -> c_5()}
The usable rules for this path are empty.
We have oriented the usable rules with the following strongly linear interpretation:
Interpretation Functions:
f(x1, x2) = [0] x1 + [0] x2 + [0]
nil() = [0]
g(x1, x2) = [0] x1 + [0] x2 + [0]
++(x1, x2) = [0] x1 + [0] x2 + [0]
null(x1) = [0] x1 + [0]
true() = [0]
false() = [0]
mem(x1, x2) = [0] x1 + [0] x2 + [0]
or(x1, x2) = [0] x1 + [0] x2 + [0]
=(x1, x2) = [0] x1 + [0] x2 + [0]
max(x1) = [0] x1 + [0]
not(x1) = [0] x1 + [0]
max'(x1, x2) = [0] x1 + [0] x2 + [0]
u() = [0]
f^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_0() = [0]
c_1(x1) = [0] x1 + [0]
++^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_2() = [0]
c_3(x1) = [0] x1 + [0]
null^#(x1) = [0] x1 + [0]
c_4() = [0]
c_5() = [0]
mem^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_6() = [0]
c_7(x1) = [0] x1 + [0]
c_8(x1) = [0] x1 + [0]
max^#(x1) = [0] x1 + [0]
c_9() = [0]
c_10(x1) = [0] x1 + [0]
We have applied the subprocessor on the resulting DP-problem:
'Weight Gap Principle'
----------------------
Answer: YES(?,O(n^1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {null^#(g(x, y)) -> c_5()}
Weak Rules:
{ mem^#(x, max(x)) -> c_8(null^#(x))
, mem^#(g(x, y), z) -> c_7(mem^#(x, z))}
Details:
We apply the weight gap principle, strictly orienting the rules
{null^#(g(x, y)) -> c_5()}
and weakly orienting the rules
{ mem^#(x, max(x)) -> c_8(null^#(x))
, mem^#(g(x, y), z) -> c_7(mem^#(x, z))}
using the following strongly linear interpretation:
Processor 'Matrix Interpretation' oriented the following rules strictly:
{null^#(g(x, y)) -> c_5()}
Details:
Interpretation Functions:
f(x1, x2) = [0] x1 + [0] x2 + [0]
nil() = [0]
g(x1, x2) = [1] x1 + [1] x2 + [0]
++(x1, x2) = [0] x1 + [0] x2 + [0]
null(x1) = [0] x1 + [0]
true() = [0]
false() = [0]
mem(x1, x2) = [0] x1 + [0] x2 + [0]
or(x1, x2) = [0] x1 + [0] x2 + [0]
=(x1, x2) = [0] x1 + [0] x2 + [0]
max(x1) = [1] x1 + [0]
not(x1) = [0] x1 + [0]
max'(x1, x2) = [0] x1 + [0] x2 + [0]
u() = [0]
f^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_0() = [0]
c_1(x1) = [0] x1 + [0]
++^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_2() = [0]
c_3(x1) = [0] x1 + [0]
null^#(x1) = [1] x1 + [1]
c_4() = [0]
c_5() = [0]
mem^#(x1, x2) = [1] x1 + [1] x2 + [1]
c_6() = [0]
c_7(x1) = [1] x1 + [0]
c_8(x1) = [1] x1 + [0]
max^#(x1) = [0] x1 + [0]
c_9() = [0]
c_10(x1) = [0] x1 + [0]
Finally we apply the subprocessor
'Empty TRS'
-----------
Answer: YES(?,O(1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {}
Weak Rules:
{ null^#(g(x, y)) -> c_5()
, mem^#(x, max(x)) -> c_8(null^#(x))
, mem^#(g(x, y), z) -> c_7(mem^#(x, z))}
Details:
The given problem does not contain any strict rules
4) { mem^#(g(x, y), z) -> c_7(mem^#(x, z))
, mem^#(x, max(x)) -> c_8(null^#(x))
, null^#(nil()) -> c_4()}
The usable rules for this path are empty.
We have oriented the usable rules with the following strongly linear interpretation:
Interpretation Functions:
f(x1, x2) = [0] x1 + [0] x2 + [0]
nil() = [0]
g(x1, x2) = [0] x1 + [0] x2 + [0]
++(x1, x2) = [0] x1 + [0] x2 + [0]
null(x1) = [0] x1 + [0]
true() = [0]
false() = [0]
mem(x1, x2) = [0] x1 + [0] x2 + [0]
or(x1, x2) = [0] x1 + [0] x2 + [0]
=(x1, x2) = [0] x1 + [0] x2 + [0]
max(x1) = [0] x1 + [0]
not(x1) = [0] x1 + [0]
max'(x1, x2) = [0] x1 + [0] x2 + [0]
u() = [0]
f^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_0() = [0]
c_1(x1) = [0] x1 + [0]
++^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_2() = [0]
c_3(x1) = [0] x1 + [0]
null^#(x1) = [0] x1 + [0]
c_4() = [0]
c_5() = [0]
mem^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_6() = [0]
c_7(x1) = [0] x1 + [0]
c_8(x1) = [0] x1 + [0]
max^#(x1) = [0] x1 + [0]
c_9() = [0]
c_10(x1) = [0] x1 + [0]
We have applied the subprocessor on the resulting DP-problem:
'Weight Gap Principle'
----------------------
Answer: YES(?,O(n^1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {null^#(nil()) -> c_4()}
Weak Rules:
{ mem^#(x, max(x)) -> c_8(null^#(x))
, mem^#(g(x, y), z) -> c_7(mem^#(x, z))}
Details:
We apply the weight gap principle, strictly orienting the rules
{null^#(nil()) -> c_4()}
and weakly orienting the rules
{ mem^#(x, max(x)) -> c_8(null^#(x))
, mem^#(g(x, y), z) -> c_7(mem^#(x, z))}
using the following strongly linear interpretation:
Processor 'Matrix Interpretation' oriented the following rules strictly:
{null^#(nil()) -> c_4()}
Details:
Interpretation Functions:
f(x1, x2) = [0] x1 + [0] x2 + [0]
nil() = [0]
g(x1, x2) = [1] x1 + [1] x2 + [0]
++(x1, x2) = [0] x1 + [0] x2 + [0]
null(x1) = [0] x1 + [0]
true() = [0]
false() = [0]
mem(x1, x2) = [0] x1 + [0] x2 + [0]
or(x1, x2) = [0] x1 + [0] x2 + [0]
=(x1, x2) = [0] x1 + [0] x2 + [0]
max(x1) = [1] x1 + [0]
not(x1) = [0] x1 + [0]
max'(x1, x2) = [0] x1 + [0] x2 + [0]
u() = [0]
f^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_0() = [0]
c_1(x1) = [0] x1 + [0]
++^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_2() = [0]
c_3(x1) = [0] x1 + [0]
null^#(x1) = [1] x1 + [1]
c_4() = [0]
c_5() = [0]
mem^#(x1, x2) = [1] x1 + [1] x2 + [1]
c_6() = [0]
c_7(x1) = [1] x1 + [0]
c_8(x1) = [1] x1 + [0]
max^#(x1) = [0] x1 + [0]
c_9() = [0]
c_10(x1) = [0] x1 + [0]
Finally we apply the subprocessor
'Empty TRS'
-----------
Answer: YES(?,O(1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {}
Weak Rules:
{ null^#(nil()) -> c_4()
, mem^#(x, max(x)) -> c_8(null^#(x))
, mem^#(g(x, y), z) -> c_7(mem^#(x, z))}
Details:
The given problem does not contain any strict rules
5) { mem^#(g(x, y), z) -> c_7(mem^#(x, z))
, mem^#(nil(), y) -> c_6()}
The usable rules for this path are empty.
We have oriented the usable rules with the following strongly linear interpretation:
Interpretation Functions:
f(x1, x2) = [0] x1 + [0] x2 + [0]
nil() = [0]
g(x1, x2) = [0] x1 + [0] x2 + [0]
++(x1, x2) = [0] x1 + [0] x2 + [0]
null(x1) = [0] x1 + [0]
true() = [0]
false() = [0]
mem(x1, x2) = [0] x1 + [0] x2 + [0]
or(x1, x2) = [0] x1 + [0] x2 + [0]
=(x1, x2) = [0] x1 + [0] x2 + [0]
max(x1) = [0] x1 + [0]
not(x1) = [0] x1 + [0]
max'(x1, x2) = [0] x1 + [0] x2 + [0]
u() = [0]
f^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_0() = [0]
c_1(x1) = [0] x1 + [0]
++^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_2() = [0]
c_3(x1) = [0] x1 + [0]
null^#(x1) = [0] x1 + [0]
c_4() = [0]
c_5() = [0]
mem^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_6() = [0]
c_7(x1) = [0] x1 + [0]
c_8(x1) = [0] x1 + [0]
max^#(x1) = [0] x1 + [0]
c_9() = [0]
c_10(x1) = [0] x1 + [0]
We have applied the subprocessor on the resulting DP-problem:
'Weight Gap Principle'
----------------------
Answer: YES(?,O(n^1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {mem^#(nil(), y) -> c_6()}
Weak Rules: {mem^#(g(x, y), z) -> c_7(mem^#(x, z))}
Details:
We apply the weight gap principle, strictly orienting the rules
{mem^#(nil(), y) -> c_6()}
and weakly orienting the rules
{mem^#(g(x, y), z) -> c_7(mem^#(x, z))}
using the following strongly linear interpretation:
Processor 'Matrix Interpretation' oriented the following rules strictly:
{mem^#(nil(), y) -> c_6()}
Details:
Interpretation Functions:
f(x1, x2) = [0] x1 + [0] x2 + [0]
nil() = [0]
g(x1, x2) = [1] x1 + [1] x2 + [0]
++(x1, x2) = [0] x1 + [0] x2 + [0]
null(x1) = [0] x1 + [0]
true() = [0]
false() = [0]
mem(x1, x2) = [0] x1 + [0] x2 + [0]
or(x1, x2) = [0] x1 + [0] x2 + [0]
=(x1, x2) = [0] x1 + [0] x2 + [0]
max(x1) = [0] x1 + [0]
not(x1) = [0] x1 + [0]
max'(x1, x2) = [0] x1 + [0] x2 + [0]
u() = [0]
f^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_0() = [0]
c_1(x1) = [0] x1 + [0]
++^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_2() = [0]
c_3(x1) = [0] x1 + [0]
null^#(x1) = [0] x1 + [0]
c_4() = [0]
c_5() = [0]
mem^#(x1, x2) = [1] x1 + [1] x2 + [1]
c_6() = [0]
c_7(x1) = [1] x1 + [0]
c_8(x1) = [0] x1 + [0]
max^#(x1) = [0] x1 + [0]
c_9() = [0]
c_10(x1) = [0] x1 + [0]
Finally we apply the subprocessor
'Empty TRS'
-----------
Answer: YES(?,O(1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {}
Weak Rules:
{ mem^#(nil(), y) -> c_6()
, mem^#(g(x, y), z) -> c_7(mem^#(x, z))}
Details:
The given problem does not contain any strict rules
6) { mem^#(g(x, y), z) -> c_7(mem^#(x, z))
, mem^#(x, max(x)) -> c_8(null^#(x))}
The usable rules for this path are empty.
We have oriented the usable rules with the following strongly linear interpretation:
Interpretation Functions:
f(x1, x2) = [0] x1 + [0] x2 + [0]
nil() = [0]
g(x1, x2) = [0] x1 + [0] x2 + [0]
++(x1, x2) = [0] x1 + [0] x2 + [0]
null(x1) = [0] x1 + [0]
true() = [0]
false() = [0]
mem(x1, x2) = [0] x1 + [0] x2 + [0]
or(x1, x2) = [0] x1 + [0] x2 + [0]
=(x1, x2) = [0] x1 + [0] x2 + [0]
max(x1) = [0] x1 + [0]
not(x1) = [0] x1 + [0]
max'(x1, x2) = [0] x1 + [0] x2 + [0]
u() = [0]
f^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_0() = [0]
c_1(x1) = [0] x1 + [0]
++^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_2() = [0]
c_3(x1) = [0] x1 + [0]
null^#(x1) = [0] x1 + [0]
c_4() = [0]
c_5() = [0]
mem^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_6() = [0]
c_7(x1) = [0] x1 + [0]
c_8(x1) = [0] x1 + [0]
max^#(x1) = [0] x1 + [0]
c_9() = [0]
c_10(x1) = [0] x1 + [0]
We have applied the subprocessor on the resulting DP-problem:
'Weight Gap Principle'
----------------------
Answer: YES(?,O(n^1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {mem^#(x, max(x)) -> c_8(null^#(x))}
Weak Rules: {mem^#(g(x, y), z) -> c_7(mem^#(x, z))}
Details:
We apply the weight gap principle, strictly orienting the rules
{mem^#(x, max(x)) -> c_8(null^#(x))}
and weakly orienting the rules
{mem^#(g(x, y), z) -> c_7(mem^#(x, z))}
using the following strongly linear interpretation:
Processor 'Matrix Interpretation' oriented the following rules strictly:
{mem^#(x, max(x)) -> c_8(null^#(x))}
Details:
Interpretation Functions:
f(x1, x2) = [0] x1 + [0] x2 + [0]
nil() = [0]
g(x1, x2) = [1] x1 + [1] x2 + [0]
++(x1, x2) = [0] x1 + [0] x2 + [0]
null(x1) = [0] x1 + [0]
true() = [0]
false() = [0]
mem(x1, x2) = [0] x1 + [0] x2 + [0]
or(x1, x2) = [0] x1 + [0] x2 + [0]
=(x1, x2) = [0] x1 + [0] x2 + [0]
max(x1) = [1] x1 + [0]
not(x1) = [0] x1 + [0]
max'(x1, x2) = [0] x1 + [0] x2 + [0]
u() = [0]
f^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_0() = [0]
c_1(x1) = [0] x1 + [0]
++^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_2() = [0]
c_3(x1) = [0] x1 + [0]
null^#(x1) = [1] x1 + [0]
c_4() = [0]
c_5() = [0]
mem^#(x1, x2) = [1] x1 + [1] x2 + [1]
c_6() = [0]
c_7(x1) = [1] x1 + [0]
c_8(x1) = [1] x1 + [0]
max^#(x1) = [0] x1 + [0]
c_9() = [0]
c_10(x1) = [0] x1 + [0]
Finally we apply the subprocessor
'Empty TRS'
-----------
Answer: YES(?,O(1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {}
Weak Rules:
{ mem^#(x, max(x)) -> c_8(null^#(x))
, mem^#(g(x, y), z) -> c_7(mem^#(x, z))}
Details:
The given problem does not contain any strict rules
7) { f^#(x, g(y, z)) -> c_1(f^#(x, y))
, f^#(x, nil()) -> c_0()}
The usable rules for this path are empty.
We have oriented the usable rules with the following strongly linear interpretation:
Interpretation Functions:
f(x1, x2) = [0] x1 + [0] x2 + [0]
nil() = [0]
g(x1, x2) = [0] x1 + [0] x2 + [0]
++(x1, x2) = [0] x1 + [0] x2 + [0]
null(x1) = [0] x1 + [0]
true() = [0]
false() = [0]
mem(x1, x2) = [0] x1 + [0] x2 + [0]
or(x1, x2) = [0] x1 + [0] x2 + [0]
=(x1, x2) = [0] x1 + [0] x2 + [0]
max(x1) = [0] x1 + [0]
not(x1) = [0] x1 + [0]
max'(x1, x2) = [0] x1 + [0] x2 + [0]
u() = [0]
f^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_0() = [0]
c_1(x1) = [0] x1 + [0]
++^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_2() = [0]
c_3(x1) = [0] x1 + [0]
null^#(x1) = [0] x1 + [0]
c_4() = [0]
c_5() = [0]
mem^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_6() = [0]
c_7(x1) = [0] x1 + [0]
c_8(x1) = [0] x1 + [0]
max^#(x1) = [0] x1 + [0]
c_9() = [0]
c_10(x1) = [0] x1 + [0]
We have applied the subprocessor on the resulting DP-problem:
'Weight Gap Principle'
----------------------
Answer: YES(?,O(n^1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {f^#(x, nil()) -> c_0()}
Weak Rules: {f^#(x, g(y, z)) -> c_1(f^#(x, y))}
Details:
We apply the weight gap principle, strictly orienting the rules
{f^#(x, nil()) -> c_0()}
and weakly orienting the rules
{f^#(x, g(y, z)) -> c_1(f^#(x, y))}
using the following strongly linear interpretation:
Processor 'Matrix Interpretation' oriented the following rules strictly:
{f^#(x, nil()) -> c_0()}
Details:
Interpretation Functions:
f(x1, x2) = [0] x1 + [0] x2 + [0]
nil() = [0]
g(x1, x2) = [1] x1 + [1] x2 + [0]
++(x1, x2) = [0] x1 + [0] x2 + [0]
null(x1) = [0] x1 + [0]
true() = [0]
false() = [0]
mem(x1, x2) = [0] x1 + [0] x2 + [0]
or(x1, x2) = [0] x1 + [0] x2 + [0]
=(x1, x2) = [0] x1 + [0] x2 + [0]
max(x1) = [0] x1 + [0]
not(x1) = [0] x1 + [0]
max'(x1, x2) = [0] x1 + [0] x2 + [0]
u() = [0]
f^#(x1, x2) = [1] x1 + [1] x2 + [1]
c_0() = [0]
c_1(x1) = [1] x1 + [0]
++^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_2() = [0]
c_3(x1) = [0] x1 + [0]
null^#(x1) = [0] x1 + [0]
c_4() = [0]
c_5() = [0]
mem^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_6() = [0]
c_7(x1) = [0] x1 + [0]
c_8(x1) = [0] x1 + [0]
max^#(x1) = [0] x1 + [0]
c_9() = [0]
c_10(x1) = [0] x1 + [0]
Finally we apply the subprocessor
'Empty TRS'
-----------
Answer: YES(?,O(1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {}
Weak Rules:
{ f^#(x, nil()) -> c_0()
, f^#(x, g(y, z)) -> c_1(f^#(x, y))}
Details:
The given problem does not contain any strict rules
8) { ++^#(x, g(y, z)) -> c_3(++^#(x, y))
, ++^#(x, nil()) -> c_2()}
The usable rules for this path are empty.
We have oriented the usable rules with the following strongly linear interpretation:
Interpretation Functions:
f(x1, x2) = [0] x1 + [0] x2 + [0]
nil() = [0]
g(x1, x2) = [0] x1 + [0] x2 + [0]
++(x1, x2) = [0] x1 + [0] x2 + [0]
null(x1) = [0] x1 + [0]
true() = [0]
false() = [0]
mem(x1, x2) = [0] x1 + [0] x2 + [0]
or(x1, x2) = [0] x1 + [0] x2 + [0]
=(x1, x2) = [0] x1 + [0] x2 + [0]
max(x1) = [0] x1 + [0]
not(x1) = [0] x1 + [0]
max'(x1, x2) = [0] x1 + [0] x2 + [0]
u() = [0]
f^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_0() = [0]
c_1(x1) = [0] x1 + [0]
++^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_2() = [0]
c_3(x1) = [0] x1 + [0]
null^#(x1) = [0] x1 + [0]
c_4() = [0]
c_5() = [0]
mem^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_6() = [0]
c_7(x1) = [0] x1 + [0]
c_8(x1) = [0] x1 + [0]
max^#(x1) = [0] x1 + [0]
c_9() = [0]
c_10(x1) = [0] x1 + [0]
We have applied the subprocessor on the resulting DP-problem:
'Weight Gap Principle'
----------------------
Answer: YES(?,O(n^1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {++^#(x, nil()) -> c_2()}
Weak Rules: {++^#(x, g(y, z)) -> c_3(++^#(x, y))}
Details:
We apply the weight gap principle, strictly orienting the rules
{++^#(x, nil()) -> c_2()}
and weakly orienting the rules
{++^#(x, g(y, z)) -> c_3(++^#(x, y))}
using the following strongly linear interpretation:
Processor 'Matrix Interpretation' oriented the following rules strictly:
{++^#(x, nil()) -> c_2()}
Details:
Interpretation Functions:
f(x1, x2) = [0] x1 + [0] x2 + [0]
nil() = [0]
g(x1, x2) = [1] x1 + [1] x2 + [0]
++(x1, x2) = [0] x1 + [0] x2 + [0]
null(x1) = [0] x1 + [0]
true() = [0]
false() = [0]
mem(x1, x2) = [0] x1 + [0] x2 + [0]
or(x1, x2) = [0] x1 + [0] x2 + [0]
=(x1, x2) = [0] x1 + [0] x2 + [0]
max(x1) = [0] x1 + [0]
not(x1) = [0] x1 + [0]
max'(x1, x2) = [0] x1 + [0] x2 + [0]
u() = [0]
f^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_0() = [0]
c_1(x1) = [0] x1 + [0]
++^#(x1, x2) = [1] x1 + [1] x2 + [1]
c_2() = [0]
c_3(x1) = [1] x1 + [0]
null^#(x1) = [0] x1 + [0]
c_4() = [0]
c_5() = [0]
mem^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_6() = [0]
c_7(x1) = [0] x1 + [0]
c_8(x1) = [0] x1 + [0]
max^#(x1) = [0] x1 + [0]
c_9() = [0]
c_10(x1) = [0] x1 + [0]
Finally we apply the subprocessor
'Empty TRS'
-----------
Answer: YES(?,O(1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {}
Weak Rules:
{ ++^#(x, nil()) -> c_2()
, ++^#(x, g(y, z)) -> c_3(++^#(x, y))}
Details:
The given problem does not contain any strict rules
9) {++^#(x, g(y, z)) -> c_3(++^#(x, y))}
The usable rules for this path are empty.
We have oriented the usable rules with the following strongly linear interpretation:
Interpretation Functions:
f(x1, x2) = [0] x1 + [0] x2 + [0]
nil() = [0]
g(x1, x2) = [0] x1 + [0] x2 + [0]
++(x1, x2) = [0] x1 + [0] x2 + [0]
null(x1) = [0] x1 + [0]
true() = [0]
false() = [0]
mem(x1, x2) = [0] x1 + [0] x2 + [0]
or(x1, x2) = [0] x1 + [0] x2 + [0]
=(x1, x2) = [0] x1 + [0] x2 + [0]
max(x1) = [0] x1 + [0]
not(x1) = [0] x1 + [0]
max'(x1, x2) = [0] x1 + [0] x2 + [0]
u() = [0]
f^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_0() = [0]
c_1(x1) = [0] x1 + [0]
++^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_2() = [0]
c_3(x1) = [0] x1 + [0]
null^#(x1) = [0] x1 + [0]
c_4() = [0]
c_5() = [0]
mem^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_6() = [0]
c_7(x1) = [0] x1 + [0]
c_8(x1) = [0] x1 + [0]
max^#(x1) = [0] x1 + [0]
c_9() = [0]
c_10(x1) = [0] x1 + [0]
We have applied the subprocessor on the resulting DP-problem:
'Weight Gap Principle'
----------------------
Answer: YES(?,O(n^1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {++^#(x, g(y, z)) -> c_3(++^#(x, y))}
Weak Rules: {}
Details:
We apply the weight gap principle, strictly orienting the rules
{++^#(x, g(y, z)) -> c_3(++^#(x, y))}
and weakly orienting the rules
{}
using the following strongly linear interpretation:
Processor 'Matrix Interpretation' oriented the following rules strictly:
{++^#(x, g(y, z)) -> c_3(++^#(x, y))}
Details:
Interpretation Functions:
f(x1, x2) = [0] x1 + [0] x2 + [0]
nil() = [0]
g(x1, x2) = [1] x1 + [1] x2 + [8]
++(x1, x2) = [0] x1 + [0] x2 + [0]
null(x1) = [0] x1 + [0]
true() = [0]
false() = [0]
mem(x1, x2) = [0] x1 + [0] x2 + [0]
or(x1, x2) = [0] x1 + [0] x2 + [0]
=(x1, x2) = [0] x1 + [0] x2 + [0]
max(x1) = [0] x1 + [0]
not(x1) = [0] x1 + [0]
max'(x1, x2) = [0] x1 + [0] x2 + [0]
u() = [0]
f^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_0() = [0]
c_1(x1) = [0] x1 + [0]
++^#(x1, x2) = [1] x1 + [1] x2 + [1]
c_2() = [0]
c_3(x1) = [1] x1 + [3]
null^#(x1) = [0] x1 + [0]
c_4() = [0]
c_5() = [0]
mem^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_6() = [0]
c_7(x1) = [0] x1 + [0]
c_8(x1) = [0] x1 + [0]
max^#(x1) = [0] x1 + [0]
c_9() = [0]
c_10(x1) = [0] x1 + [0]
Finally we apply the subprocessor
'Empty TRS'
-----------
Answer: YES(?,O(1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {}
Weak Rules: {++^#(x, g(y, z)) -> c_3(++^#(x, y))}
Details:
The given problem does not contain any strict rules
10)
{mem^#(g(x, y), z) -> c_7(mem^#(x, z))}
The usable rules for this path are empty.
We have oriented the usable rules with the following strongly linear interpretation:
Interpretation Functions:
f(x1, x2) = [0] x1 + [0] x2 + [0]
nil() = [0]
g(x1, x2) = [0] x1 + [0] x2 + [0]
++(x1, x2) = [0] x1 + [0] x2 + [0]
null(x1) = [0] x1 + [0]
true() = [0]
false() = [0]
mem(x1, x2) = [0] x1 + [0] x2 + [0]
or(x1, x2) = [0] x1 + [0] x2 + [0]
=(x1, x2) = [0] x1 + [0] x2 + [0]
max(x1) = [0] x1 + [0]
not(x1) = [0] x1 + [0]
max'(x1, x2) = [0] x1 + [0] x2 + [0]
u() = [0]
f^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_0() = [0]
c_1(x1) = [0] x1 + [0]
++^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_2() = [0]
c_3(x1) = [0] x1 + [0]
null^#(x1) = [0] x1 + [0]
c_4() = [0]
c_5() = [0]
mem^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_6() = [0]
c_7(x1) = [0] x1 + [0]
c_8(x1) = [0] x1 + [0]
max^#(x1) = [0] x1 + [0]
c_9() = [0]
c_10(x1) = [0] x1 + [0]
We have applied the subprocessor on the resulting DP-problem:
'Weight Gap Principle'
----------------------
Answer: YES(?,O(n^1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {mem^#(g(x, y), z) -> c_7(mem^#(x, z))}
Weak Rules: {}
Details:
We apply the weight gap principle, strictly orienting the rules
{mem^#(g(x, y), z) -> c_7(mem^#(x, z))}
and weakly orienting the rules
{}
using the following strongly linear interpretation:
Processor 'Matrix Interpretation' oriented the following rules strictly:
{mem^#(g(x, y), z) -> c_7(mem^#(x, z))}
Details:
Interpretation Functions:
f(x1, x2) = [0] x1 + [0] x2 + [0]
nil() = [0]
g(x1, x2) = [1] x1 + [1] x2 + [8]
++(x1, x2) = [0] x1 + [0] x2 + [0]
null(x1) = [0] x1 + [0]
true() = [0]
false() = [0]
mem(x1, x2) = [0] x1 + [0] x2 + [0]
or(x1, x2) = [0] x1 + [0] x2 + [0]
=(x1, x2) = [0] x1 + [0] x2 + [0]
max(x1) = [0] x1 + [0]
not(x1) = [0] x1 + [0]
max'(x1, x2) = [0] x1 + [0] x2 + [0]
u() = [0]
f^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_0() = [0]
c_1(x1) = [0] x1 + [0]
++^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_2() = [0]
c_3(x1) = [0] x1 + [0]
null^#(x1) = [0] x1 + [0]
c_4() = [0]
c_5() = [0]
mem^#(x1, x2) = [1] x1 + [1] x2 + [1]
c_6() = [0]
c_7(x1) = [1] x1 + [3]
c_8(x1) = [0] x1 + [0]
max^#(x1) = [0] x1 + [0]
c_9() = [0]
c_10(x1) = [0] x1 + [0]
Finally we apply the subprocessor
'Empty TRS'
-----------
Answer: YES(?,O(1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {}
Weak Rules: {mem^#(g(x, y), z) -> c_7(mem^#(x, z))}
Details:
The given problem does not contain any strict rules
11)
{f^#(x, g(y, z)) -> c_1(f^#(x, y))}
The usable rules for this path are empty.
We have oriented the usable rules with the following strongly linear interpretation:
Interpretation Functions:
f(x1, x2) = [0] x1 + [0] x2 + [0]
nil() = [0]
g(x1, x2) = [0] x1 + [0] x2 + [0]
++(x1, x2) = [0] x1 + [0] x2 + [0]
null(x1) = [0] x1 + [0]
true() = [0]
false() = [0]
mem(x1, x2) = [0] x1 + [0] x2 + [0]
or(x1, x2) = [0] x1 + [0] x2 + [0]
=(x1, x2) = [0] x1 + [0] x2 + [0]
max(x1) = [0] x1 + [0]
not(x1) = [0] x1 + [0]
max'(x1, x2) = [0] x1 + [0] x2 + [0]
u() = [0]
f^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_0() = [0]
c_1(x1) = [0] x1 + [0]
++^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_2() = [0]
c_3(x1) = [0] x1 + [0]
null^#(x1) = [0] x1 + [0]
c_4() = [0]
c_5() = [0]
mem^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_6() = [0]
c_7(x1) = [0] x1 + [0]
c_8(x1) = [0] x1 + [0]
max^#(x1) = [0] x1 + [0]
c_9() = [0]
c_10(x1) = [0] x1 + [0]
We have applied the subprocessor on the resulting DP-problem:
'Weight Gap Principle'
----------------------
Answer: YES(?,O(n^1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {f^#(x, g(y, z)) -> c_1(f^#(x, y))}
Weak Rules: {}
Details:
We apply the weight gap principle, strictly orienting the rules
{f^#(x, g(y, z)) -> c_1(f^#(x, y))}
and weakly orienting the rules
{}
using the following strongly linear interpretation:
Processor 'Matrix Interpretation' oriented the following rules strictly:
{f^#(x, g(y, z)) -> c_1(f^#(x, y))}
Details:
Interpretation Functions:
f(x1, x2) = [0] x1 + [0] x2 + [0]
nil() = [0]
g(x1, x2) = [1] x1 + [1] x2 + [8]
++(x1, x2) = [0] x1 + [0] x2 + [0]
null(x1) = [0] x1 + [0]
true() = [0]
false() = [0]
mem(x1, x2) = [0] x1 + [0] x2 + [0]
or(x1, x2) = [0] x1 + [0] x2 + [0]
=(x1, x2) = [0] x1 + [0] x2 + [0]
max(x1) = [0] x1 + [0]
not(x1) = [0] x1 + [0]
max'(x1, x2) = [0] x1 + [0] x2 + [0]
u() = [0]
f^#(x1, x2) = [1] x1 + [1] x2 + [1]
c_0() = [0]
c_1(x1) = [1] x1 + [3]
++^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_2() = [0]
c_3(x1) = [0] x1 + [0]
null^#(x1) = [0] x1 + [0]
c_4() = [0]
c_5() = [0]
mem^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_6() = [0]
c_7(x1) = [0] x1 + [0]
c_8(x1) = [0] x1 + [0]
max^#(x1) = [0] x1 + [0]
c_9() = [0]
c_10(x1) = [0] x1 + [0]
Finally we apply the subprocessor
'Empty TRS'
-----------
Answer: YES(?,O(1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {}
Weak Rules: {f^#(x, g(y, z)) -> c_1(f^#(x, y))}
Details:
The given problem does not contain any strict rules